﻿/*
 * Here we implement graph searching.  
 * 
 * A graph consists of Nodes and Archs.  Node B is a Sibling of A if there is an Arch from A to B.
 * A is the Parent of B
 * 
 * A generic search contains a Frontier of paths (actually of the last Node in the path)
 * from the start Node that has been explored.  
 * 
 * When using search, you have to:
 *   - Decide what is contained in the Node -- call it the NodeContentType
 *   - Decide what is the ArchType
 *   - Decide on a Start Node
 *   - Decide on a Goal Node  (it is possible that a search is optimising and has no goal)
 *   - Decide on AddSiblings method -- given the Node, and the remaining Frontier, give a list of 
 *       <ArchContentType,ArchNodeType> pairs that continues the search
 *   - Decide on a Select method to choose the net Node in the Frontier to expand
 */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace PacmanAI.Graphs
{
    public abstract class Graph<TNodeContent, TArch>
    {

        public class NodeList : List<Node>
        {
            public override string ToString()
            {
                StringBuilder b = new StringBuilder();
                b.Append("[");
                foreach (var n in this)
                    b.AppendFormat("{0};", n);
                b.Append("]");
                return b.ToString();
            }
        }

        public class Node
        {
            /// <summary>
            /// Distance from Root Node
            /// </summary>
            public readonly int Depth;
            public readonly TNodeContent Content;
            public readonly Node Parent;
            public readonly TArch ArchFromParent;
            public NodeList Siblings;

            public Node(TNodeContent nc, TArch arch, Node parent, int depth)
            {
                Depth = depth;
                Content = nc;
                ArchFromParent = arch;
                Parent = parent;
            }

            public bool IsRoot
            {
                get { return Depth == 0; }
            }

            public bool IsOnEdge
            {
                get { return Siblings == null || Siblings.Count == 0; }
            }

            public void Accept(Visitor v)
            {
                v(this);
                if (!IsOnEdge)
                {
                    foreach (var s in Siblings)
                        s.Accept(v);
                }
            }

            public bool PathContains(Predicate<Node> pred)
            {
                NodeList r = new NodeList();
                var n = this;
                while (!n.IsRoot)
                {
                    if (pred(n))
                        return true;
                    n = n.Parent;
                };
                return pred(n);
            }

            public TArch ArchFromRoot()
            {
                return SiblingOfRootOfPath().ArchFromParent;
            }

            private Node SiblingOfRootOfPath()
            {                
                var n = this;
                while (!n.Parent.IsRoot)
                    n = n.Parent;
                return n;
            }


            private Node RootOfPath()
            {
                var n = this;
                while (!n.IsRoot)
                    n = n.Parent;
                return n;
            }

            public NodeList Path()
            {
                NodeList r = new NodeList();
                var n = this;
                while (!n.IsRoot)
                {
                    r.Add(n);
                    n = n.Parent;
                };
                r.Add(n); // root node
                r.Reverse();
                return r;
            }

            public override string ToString()
            {
                if (!IsRoot)
                    return string.Format("{0}:{1}", ArchFromParent, Content);
                else
                    return Content.ToString();
            }
        }

        public delegate Node Selector(NodeList frontier);
        public delegate void Visitor(Node element);


        protected abstract void GetSiblings(Node selected, NodeList frontier, Dictionary<TArch, TNodeContent> siblings);

        protected abstract bool IsGoal(Node n);

        public Node Root;
        public NodeList Frontier;
        public Node GoalNode;

        public bool Search(TNodeContent rootContent, Selector select)
        {
            Root = new Node(rootContent, default(TArch), null, 0);
            GoalNode = null;
            Frontier = new NodeList();
            Frontier.Add(Root);
            Dictionary<TArch, TNodeContent> sibs = new Dictionary<TArch, TNodeContent>();
            while (Frontier.Count > 0 && GoalNode == null)
            {
                Node next = select(Frontier);
                GetSiblings(next, Frontier, sibs);
                Frontier.Remove(next);
                next.Siblings = new NodeList();
                foreach (var i in sibs)
                {
                    Node s = new Node(i.Value, i.Key, next, next.Depth + 1);
                    if (IsGoal(s))
                        GoalNode = s;
                    next.Siblings.Add(s);
                    Frontier.Add(s);
                }
                sibs.Clear();
            }
            return GoalNode != null;
        }


        public NodeList EndPoints()
        {
            NodeList r = new NodeList();
            Visitor collector = delegate(Node e)
            {
                if (e.IsOnEdge)
                    r.Add(e);
            };
            Root.Accept(collector);
            return r;
        }
        

        public static Selector BreadthFirstSearch // or LIFO
            = delegate(NodeList frontier) { return frontier[0]; };


        public override string ToString()
        {
            StringBuilder b = new StringBuilder();            
            foreach (var ep in EndPoints())
            {
                b.AppendLine(ep.Path().ToString());
            }
            return b.ToString();
        }

    }

    public interface IGraphContent<TNode, TArch>
    {
        void CollectSiblings(Graph<TNode,TArch>.Node path, Dictionary<TArch, TNode> siblings);
        int DistanceFromGoal {get; }
    }

    class SimpleGraph<TNode, TArch> : Graph<TNode, TArch>
        where TNode : IGraphContent<TNode,TArch>
    {

        protected override void GetSiblings(Graph<TNode, TArch>.Node selected, Graph<TNode, TArch>.NodeList frontier, Dictionary<TArch, TNode> siblings)
        {
            selected.Content.CollectSiblings(selected, siblings);
        }

        public bool Search(TNode rootContent)
        {
            Comparison<Node> closest =
                delegate(Node a, Node b)
                { return - (a.Content.DistanceFromGoal.CompareTo(b.Content.DistanceFromGoal)); };

            Selector bestFirst = delegate (NodeList f)
            {
                return Frontier.FindBest(closest);
            };
            return base.Search(rootContent,bestFirst);
                
        }


        protected override bool IsGoal(Graph<TNode, TArch>.Node n)
        {
            return n.Content.DistanceFromGoal == 0;
        }
    }

}
